package chapter04_RecursionAndDynamic;

/**
 * 描述：
 * 返回从矩阵左上角到矩阵右下角的最小路径和,每次只能往下或者往右走
 *
 * @author hl
 * @date 2021/6/4 8:44
 */
public class MinPathSum {
    public static void main(String[] args) {
        int[][] matrix = {{1, 3, 5, 9}, {8, 1, 3, 4}, {5, 0, 6, 1}, {8, 8, 4, 0}};
        MinPathSum minPathSum = new MinPathSum();
        int sum1 = minPathSum.minPathSum2(matrix);
        int sum2 = minPathSum.minPathSum3(matrix);
        int sum3 = minPathSum.minPathSum32(matrix);
        System.out.println(sum1);
        System.out.println(sum2);
        System.out.println(sum3);
    }

    /**
     * 暴力递归
     *
     * @param matrix
     * @return
     */
    public int minPathSum(int[][] matrix) {
        boolean[] flag = new boolean[1];
        flag[0] = true;
        return process(matrix, 0, 0, flag);
    }

    private int process(int[][] matrix, int i, int j, boolean[] flag) {
        if (i >= matrix.length || j >= matrix[i].length) {
            flag[0] = false;
            return 0;
        }
        if (i == matrix.length - 1 && j == matrix[i].length - 1) {
            flag[0] = true;
            return matrix[i][j];
        }
        int ds = process(matrix, i + 1, j, flag);
        boolean isAbleD = flag[0];
        int rs = process(matrix, i, j + 1, flag);
        boolean isAbleR = flag[0];
        if (isAbleD && isAbleR) {
            return ds < rs ? ds + matrix[i][j] : rs + matrix[i][j];
        }
        return isAbleD ? ds + matrix[i][j] : rs + matrix[i][j];
    }

    /**
     * 动态规划，时间复杂度为O(M * N)，空间复杂度为O(M * N)
     *
     * @param matrix
     * @return
     */
    public int minPathSum2(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) + matrix[i][j];
            }
        }
        return dp[0][0];
    }

    /**
     * 动态规划 + 滚动数组，压缩空间复杂度为O(min{M, N})
     *
     * @param matrix
     * @return
     */
    public int minPathSum3(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        if (m < n) {
            int temp = m;
            m = n;
            n = temp;
        }
        int[] dp = new int[n + 1];
        for (int j = m - 1; j >= 0; j--) {
            for (int i = n - 1; i >= 0; i--) {
                dp[i] = Math.min(dp[i], dp[i + 1]) + matrix[i][j];
            }
        }
        return dp[0];
    }

    /**
     * 从左上下到右下角
     * @param matrix
     * @return
     */
    public int minPathSum32(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        int less = Math.min(matrix.length, matrix[0].length);//行数与列数较小的为less
        int more = Math.min(matrix.length, matrix[0].length);//行数与列数较大的为more
        boolean rowmore = more == matrix.length;    //哪一列更大
        int[] dp = new int[less];//更小的一列作为dp数组
        dp[0] = matrix[0][0];
        for (int i = 1; i < less; i++) {
            dp[i] = dp[i - 1] +  (rowmore ? matrix[0][i] : matrix[i][0]);
        }
        for (int i = 1; i < more; i++) {
            dp[0] = dp[0] + (rowmore ? matrix[i][0] : matrix[0][i]);
            for (int j = 1; j < less; j++) {
                dp[j] = Math.min(dp[j], dp[j - 1]) + (rowmore ? matrix[i][j] : matrix[j][i]);
            }
        }
        return dp[less - 1];
    }
}
